The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology. Increasingly, public and private communications networks are being built and expanded using various packet technologies, such as Internet Protocol (IP).
A network device, such as a switch or router, typically receives, processes, and forwards or discards a packet. For example, an enqueuing component of such a device receives a stream of various sized packets which are accumulated in an input buffer. Each packet is analyzed, and an appropriate amount of memory space is allocated to store the packet. The packet is stored in memory, while certain attributes (e.g., destination information and other information typically derived from a packet header or other source) are maintained in separate memory. Once the entire packet is written into memory, the packet becomes eligible for processing, and an indicator of the packet is typically placed in an appropriate destination queue for being serviced according to some scheduling methodology.
When there is a contention for resources, such as on output links of a packet switching system or interface or even for compute cycles in a computing device, it is important for resources to be allocated or scheduled according to some fairness policy. Moreover, the amount of work required to schedule and to enqueue and dequeue a packet or other scheduled item is important, especially as the operating rate of systems increase.
Ordinary time division multiplexing (TDM) is a method commonly used for sharing a common resource between several clients. All scheduled clients are served one at a time at predetermined times and for pre-allocated time periods, which is a very useful property for many applications. This method is often used for multiplexing multiple synchronous items over a higher speed communications link, such as that used for multiplexing multiple telephone calls over a single facility or interleaving packets. However, in a dynamic environment wherein items may not require the full amount of their allocated time slot such as when an item may only require none or only a portion of a particular allocated time slot, then bandwidth of the resource is typically wasted.
Ordinary round-robin (RR) is a another method commonly used for sharing a common resource between several clients. All clients are served in a cyclic order. In each round every client will be served if it is eligible. When served, each client is permitted to send one packet. Servicing of queues is simple to implement and can be done in constant time, but, due to the varying size of packets, does not allocate bandwidth fairly. For example, certain higher priority or larger bandwidth ports or streams of packets many not get their desired amount of bandwidth, which may especially be the case when serving one large and numerous smaller traffic streams or when different priorities of traffic are scheduled.
In some scenarios, high priority (e.g., low latency), guaranteed bandwidth, best effort traffic (e.g., spare bandwidth) and other classifications of traffic compete for a common resource. Various known scheduling methods are designed to provide isolation, prioritization, and fair bandwidth allocation to traffic competing for a common resource. These are known as fair queuing methods. Some examples are Weighted Fair Queuing (WFQ), Self-Clocked Fair Queuing (SCFQ), and Deficit Round Robin/Surplus Round Robin (referred to as DRR).
WFQ, and SCFQ depend upon arrival times as well as previous link utilization in order to calculate the next best packet to send. The accepted “ideal” behavior is bit-by-bit round robin, which states that the next packet to send should be the packet which would have completed if all packets currently in the system send one bit each round robin (which is typically not practical in a packet based system). The inclusion of arrival times in the scheduling method, in order to calculate theoretical ideal departure times, typically requires insertion into a sorted list which is known to be an O(log N) problem worst case where N is the number of packets already enqueued.
DRR is a method used for sharing a common resource between several clients with different ratios between clients (i.e., some clients are allowed to consume more of the resources than others). The ratio between clients is typically defined by a parameter called a quantum.
DRR services queues using round-robin servicing with a quantum assigned to each queue. Unlike traditional round-robin, multiple packets up to the specified quantum can be sent resulting in each queue sending at least a quantum's worth of bytes. If the quantum for each queue is equal, then each queue will send an equal amount of bandwidth.
This DRR approach works in rounds, where a round is one round-robin iteration over the queues that have items to be sent. Typically, when the queue is scheduled, it is allowed to transmit until its deficit becomes negative, and then the next queue is served. Packets coming in on different flows are stored in different queues. Each round, each queue is allocated a quantum worth of bits, which are added to the deficit of each queue. Each queue is allowed to send out one or more packets in a DRR round, subject to the restriction that it cannot send more bits than indicated by the deficit corresponding to the queue. If there are no more packets in a queue after the queue has been serviced, the deficit corresponding to the queue is set to zero. Otherwise, the remaining amount (i.e., the deficit minus the number of bits sent) is maintained for the next round.
DRR is a method that does not depend upon actual arrival times and has complexity of O(1)—that is the amount of work required is a constant and independent of the number of packets enqueued. In order to be work conserving, a packet should be sent every time a queue is scheduled no matter its size. Thus, the quantum used in DRR should be at least one maximum packet size (MTU) to guarantee that when the quantum is added to any deficit, the resulting value is at least zero. DRR provides fair bandwidth allocation and is easy to implement. It is work conserving and, because of its O(1) properties, it scales well with higher link speeds and larger number of queues. However, its scheduling behavior deviates quite a bit from the bit-by-bit round robin “ideal”. In particular, latency for a system with N queues is Q*N where Q is the average quantum, which must be at least one maximum transport unit (MTU).
Desired are new methods and apparatus for scheduling of packets in a packet switching system, especially those which may provide good latency performance and/or have other desirable characteristics.